home *** CD-ROM | disk | FTP | other *** search
/ Mission 3 / Mission 3.zip / Mission 3.iso / texte / 7up_pd / memory.c < prev    next >
C/C++ Source or Header  |  1998-10-29  |  10KB  |  406 lines
  1. /* Eigene Speicherverwaltung. Kein Mfree(). Läuft instabil oder Bug in 7UP */
  2. /*****************************************************************************
  3. *
  4. *                                   7UP
  5. *                              Modul: MEMORY.C
  6. *                            from GNU C-Library
  7. *                   Best-/Lastfit Extension (c) TheoSoft '92
  8. *
  9. *****************************************************************************/
  10. #include <portab.h>
  11. #include <stdio.h>
  12. #include <string.h>
  13. #include <tos.h>
  14.  
  15. /* malloc, free, realloc: dynamic memory allocation */
  16. /* msize, coreleft: size of memory */
  17.  
  18. #define GET 0
  19. #define SET 1
  20.  
  21. #define FFIT 0
  22. #define BFIT 1
  23. #define LFIT 2
  24.  
  25. struct mem_chunk
  26. {
  27.    struct mem_chunk *next;
  28.    unsigned long size;
  29. };
  30.  
  31. int GetSetAllocationStrategy(int mode, int newstrategy, unsigned long *blksize);
  32. static char *_ffmalloc(unsigned long n);
  33. static char *_bfmalloc(unsigned long n);
  34. static char *_lfmalloc(unsigned long n);
  35. static char *_ffrealloc(struct mem_chunk *r, unsigned long n);
  36. static char *_blfrealloc(struct mem_chunk *r, unsigned long n);
  37.  
  38. /* linked list of free blocks */
  39. static struct mem_chunk _mchunk_free_list = { NULL, 0L };
  40.  
  41. /* minimum chunk to ask OS for (originally 4096Bytes) */
  42. static unsigned long DEFAULT_BLKSIZE=32*1024L;
  43. static int memallocstrat = FFIT;
  44.  
  45. int GetSetAllocationStrategy(int mode, int newstrategy, unsigned long *blksize)
  46. {
  47.    switch(mode)
  48.    {
  49.       case GET:
  50.          *blksize=DEFAULT_BLKSIZE;
  51.          return(memallocstrat);
  52.       case SET:
  53.          switch(newstrategy)
  54.          {
  55.             case FFIT:
  56.             case BFIT:
  57.             case LFIT:
  58.                if(*blksize>=4*1024L)
  59.                {
  60.                   DEFAULT_BLKSIZE=*blksize;
  61.                   return(memallocstrat=newstrategy);
  62.                }
  63.          }
  64.    }
  65.    return(memallocstrat);
  66. }
  67.  
  68. static char *_ffmalloc(register unsigned long n) /* first fit allocation */
  69. {
  70.    register struct mem_chunk *p, *q;
  71.    register unsigned long sz;
  72.  
  73. /* add a mem_chunk to required size and round up */
  74.    n = n + sizeof(struct mem_chunk);
  75.    n = (7L + n) & ~7L;
  76.  
  77. /* look for first block big enough in free list */
  78.    p = &_mchunk_free_list;
  79.    q = _mchunk_free_list.next;
  80.  
  81.    while ((q != NULL) && (q->size < n))
  82.    {
  83.       p = q;
  84.       q = q->next;
  85.    }
  86.  
  87. /* if not enough memory, get more from the system */
  88.    if (q == NULL)
  89.    {
  90.       sz = (n > DEFAULT_BLKSIZE ? n : DEFAULT_BLKSIZE);
  91.       q = (struct mem_chunk * )Malloc(sz);
  92.       if(!q)     /* can't alloc any more? */
  93.          return(NULL);
  94.       p->next = q;
  95.       q->size = sz;
  96.       q->next = NULL;
  97.    }
  98.  
  99.    if (q->size > (n + sizeof(struct mem_chunk)))
  100.    {           /* split, leave part of free list */
  101.       q->size -= n;
  102.       q = (struct mem_chunk * )(((unsigned long) q) + q->size);
  103.       q->size = n;
  104.    }
  105.    else
  106.    {           /* just unlink it */
  107.       p->next = q->next;
  108.    }
  109.  
  110. /* hand back ptr to after chunk desc */
  111.    return((char * )++q);
  112. }
  113.  
  114. static char *_bfmalloc(register unsigned long n) /* best fit allocation */
  115. {
  116.    register struct mem_chunk *p, *q, *bf = NULL;
  117.    register unsigned long sz, bfsize = 0xFFFFFFFF;
  118.  
  119. /* add a mem_chunk to required size and round up */
  120.    n = n + sizeof(struct mem_chunk);
  121.    n = (7L + n) & ~7L;
  122.  
  123. /* look for first block big enough in free list */
  124.    p = &_mchunk_free_list;
  125.    q = _mchunk_free_list.next;
  126.  
  127.    while ((q != NULL) && (q->size != (n + sizeof(struct mem_chunk))))
  128.    {
  129.       if(q->size > n)
  130.       {
  131.          if((q->size - n) < bfsize)
  132.          {
  133.             bf = q;
  134.             bfsize = q->size - n;
  135.          }
  136.       }
  137.       p = q;
  138.       q = q->next;
  139.    }
  140.  
  141.    if(q != NULL)   /* just unlink it */
  142.    {
  143. /* exactly found, what we want */
  144.  
  145.       p->next = q->next;
  146.    }
  147.    else
  148.    {
  149.       if(bf != NULL)
  150.       {
  151. /* this is our nearest block */
  152.  
  153.          q = bf;
  154.       }
  155.       else
  156.       {
  157. /* no smaller block available, allocate new one from OS */
  158.  
  159.          sz = (n > DEFAULT_BLKSIZE ? n : DEFAULT_BLKSIZE);
  160.          q = (struct mem_chunk * )Malloc(sz);
  161.          if(!q)     /* can't alloc any more? */
  162.             return(NULL);
  163.          p->next = q;
  164.          q->size = sz;
  165.          q->next = NULL;
  166.       }
  167.  
  168.       if (q->size > (n + sizeof(struct mem_chunk)))
  169.       {           /* split, leave part of free list */
  170.          q->size -= n;
  171.          q = (struct mem_chunk * )(((unsigned long) q) + q->size);
  172.          q->size = n;
  173.       }
  174.       else
  175.       {           /* just unlink it */
  176.          p->next = q->next;
  177.       }
  178.    }
  179.  
  180. /* hand back ptr to after chunk desc */
  181.    return((char * )++q);
  182. }
  183.  
  184. static char *_lfmalloc(register unsigned long n) /* last fit alloaction */
  185. {
  186.    register struct mem_chunk *p, *q, *lf = NULL;
  187.    register unsigned long sz;
  188.  
  189. /* add a mem_chunk to required size and round up */
  190.    n = n + sizeof(struct mem_chunk);
  191.    n = (7L + n) & ~7L;
  192.  
  193. /* look for last block big enough in free list */
  194.    p = &_mchunk_free_list;
  195.    q = _mchunk_free_list.next;
  196.  
  197.    while (q != NULL)
  198.    {
  199.       if(q->size > n)
  200.          lf = p;
  201.       p = q;
  202.       q = q->next;
  203.    }
  204.  
  205.    if (lf != NULL)
  206.    {
  207. /* this is our last block */
  208.  
  209.       p = lf;
  210.       q = lf->next;
  211.    }
  212.    else
  213.    {
  214. /* no smaller block available, allocate new one from OS */
  215.  
  216.       sz = (n > DEFAULT_BLKSIZE ? n : DEFAULT_BLKSIZE);
  217.       q = (struct mem_chunk * )Malloc(sz);
  218.       if(!q)     /* can't alloc any more? */
  219.          return(NULL);
  220.       p->next = q;
  221.       q->size = sz;
  222.       q->next = NULL;
  223.    }
  224.  
  225.    if (q->size > (n + sizeof(struct mem_chunk)))
  226.    {           /* split, leave part of free list */
  227.       q->size -= n;
  228.       q = (struct mem_chunk * )(((unsigned long) q) + q->size);
  229.       q->size = n;
  230.    }
  231.    else
  232.    {           /* just unlink it */
  233.       p->next = q->next;
  234.    }
  235.  
  236. /* hand back ptr to after chunk desc */
  237.    return((char * )++q);
  238. }
  239.  
  240. char *malloc(register unsigned long n)
  241. {
  242.    if(n==0L) /* klar */
  243.       return(NULL);
  244.    switch(memallocstrat)
  245.    {
  246.       case FFIT:
  247.          return(_ffmalloc(n));
  248.       case BFIT:
  249.          return(_bfmalloc(n));
  250.       case LFIT:
  251.          return(_lfmalloc(n));
  252.    }
  253. }
  254.  
  255. void free(register struct mem_chunk *r)
  256. {
  257.    register struct mem_chunk *p, *q, *t;
  258.  
  259.    if(r == NULL)
  260.       return;
  261.  
  262. /* move back to uncover the mem_chunk */
  263.    r--;         /* there it is! */
  264.  
  265. /* stick it into free list, preserving ascending address order */
  266.    p = &_mchunk_free_list;
  267.    q = _mchunk_free_list.next;
  268.    while (q != NULL && q < r)
  269.    {
  270.       p = q;
  271.       q = q->next;
  272.    }
  273.  
  274. /* merge after if possible */
  275.    t = (struct mem_chunk * )(((unsigned long) r) + r->size);
  276.    if (q != NULL && t >= q)
  277.    {
  278.       r->size += q->size;
  279.       q = q->next;
  280.    }
  281.    r->next = q;
  282.  
  283. /* merge before if possible, otherwise link it in */
  284.    t = (struct mem_chunk * )(((unsigned long) p) + p->size);
  285.    if (t >= r)
  286.    {
  287.       p->size += r->size;
  288.       p->next = r->next;
  289.    }
  290.    else
  291.       p->next = r;
  292. }
  293.  
  294. static char *_ffrealloc(struct mem_chunk *r, register unsigned long n) /* first fit */
  295. {
  296.    register struct mem_chunk *p, *q;
  297.    unsigned long *src, *dst;
  298.    register unsigned long sz;
  299.  
  300.    p = r - 1;
  301.    sz = (n + sizeof(struct mem_chunk) + 7L) & ~7L;
  302.  
  303.    if (p->size > sz)
  304.    {        /* block too big, split in two */
  305.       q = (struct mem_chunk * )(((unsigned long) p) + sz);
  306.       q->size = p->size - sz;
  307.       free(q + 1);
  308.       p->size = sz;
  309.    }
  310.    else
  311.    {
  312.       if (p->size < sz)
  313.       {        /* block too small, get new one */
  314.          dst = q = (struct mem_chunk * )malloc(n);
  315.          if (q != NULL)
  316.          {
  317.             src = (unsigned long * )r;
  318.             n = p->size - sizeof(struct mem_chunk);
  319.             while (n > 0)
  320.             {
  321.                *dst++ = *src++;
  322.                n -= sizeof(unsigned long);
  323.             }
  324.          }
  325.          free(r);
  326.          r = q;
  327.       }
  328.    }
  329.  
  330. /* else current block will do just fine */
  331.    return((char * )r);
  332. }
  333.  
  334. static char *_blfrealloc(struct mem_chunk *r, register unsigned long n) /* best fit */
  335. {
  336.    register struct mem_chunk *p, *q;
  337.    unsigned long *src, *dst;
  338.    register unsigned long sz;
  339.  
  340.    p = r - 1;
  341.    sz = (n + sizeof(struct mem_chunk) + 7L) & ~7L;
  342.  
  343.    if (p->size != sz)
  344.    {
  345. /* get new, best or last fit block */
  346.       dst = q = (struct mem_chunk * )malloc(n);
  347.       if (q != NULL)
  348.       {
  349.          src = (unsigned long * )r;
  350.          n = p->size - sizeof(struct mem_chunk);
  351.          memmove(dst, src, n);
  352.       }
  353.       free(r);
  354.       r = q;
  355.    }
  356.  
  357. /* else current block will do just fine */
  358.    return((char * )r);
  359. }
  360.  
  361. char *realloc(struct mem_chunk *r, register unsigned long n)
  362. {
  363.    switch(memallocstrat)
  364.    {
  365.       case FFIT:
  366.          return(_ffrealloc(r, n));
  367.       case BFIT:
  368.       case LFIT:
  369.          return(_blfrealloc(r, n));
  370.    }
  371. }
  372.  
  373. char *calloc(register unsigned long n, register unsigned long sz)
  374. {
  375.    register char *r;
  376.  
  377.    if ((r = malloc(n * sz)) != NULL)
  378.    {
  379.       memset(r, 0, n * sz);
  380.    }
  381.    return(r);
  382. }
  383.  
  384. unsigned long msize(register struct mem_chunk *r) /* size of allocated block */
  385. {
  386.    return(r?(--r)->size - sizeof(struct mem_chunk):0L);
  387. }
  388.  
  389. unsigned long coreleft(void) /* size of free mem */
  390. {
  391.    register struct mem_chunk *p, *q;
  392.    register unsigned long freemem=0L;
  393.  
  394.    p = &_mchunk_free_list;
  395.    q = _mchunk_free_list.next;
  396.  
  397.    freemem+=p->size;
  398.    while (q != NULL)
  399.    {
  400.       freemem+=q->size;
  401.       p = q;
  402.       q = q->next;
  403.    }
  404.    return(freemem+(long)Malloc(-1L));
  405. }
  406.